package com.xgh.offer;

/**
 * @ClassName Offer39
 * @Description
 * @Author xinggh
 * @Date 2020/7/1 21:51
 * @Version 1.0
 **/
public class Offer39 {
    /**
     * 剑指 Offer 39. 数组中出现次数超过一半的数字
     * 数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。
     * <p>
     * <p>
     * 示例 1:
     * <p>
     * 输入: [1, 2, 3, 2, 2, 2, 5, 4, 2]
     * 输出: 2
     * 你可以假设数组是非空的，并且给定的数组总是存在多数元素。
     */
    //方法二：不正常思路的话，用target记录上一次访问的值，count表明当前值出现的次数，
    // 如果下一个值和当前值相同那么count++；如果不同count--，
    // 减到0的时候就要更换新的target值了，因为如果存在超过数组长度一半的值，
    // 那么最后target一定会是该值。可以这样理解，count的自加和自减就是在描述一种抵消关系，
    // 由于超过一半的出现次数，导致最后的target一定会是该值。（这种方法的时间复杂度自然会小些）
    public static int majorityElement(int[] nums) {
        int target = nums[0];
        int count = 1;
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] == target) {
                count++;
            } else {
                count--;
            }
            if (count == 0) {
                target = nums[i];
                count++;
            }
        }

        return target;
    }


    public static void main(String[] args) {
        int[] nums = {1, 2, 3, 2, 2, 2, 5, 4, 2};
        System.out.println(majorityElement(nums));
    }
}
